package com.xjj.dbfs;

import javafx.util.Pair;

import java.util.HashMap;
import java.util.Map;

public class H0329LongestIncreasingPathInAMatrix {

    // 方向数组
    int[] x = {-1, 1, 0, 0};
    int[] y = {0, 0, -1, 1};

    Map<Pair<Integer, Integer>, Integer> map = new HashMap<>();

    public int longestIncreasingPath(int[][] matrix) {
        // 有向无环图,dfs,bfs


        // dfd,每个点作为起点,由于最长的起点一定是没有入度的(比周围都小于等于),可以进行裁剪
        int maxRow = matrix.length;
        int maxColumn = matrix[0].length;
        int maxDepth = 0;
        for (int row = 0; row < maxRow; row++) {
            for (int column = 0; column < maxColumn; column++) {
                // 进行裁剪
                boolean needJump = false;
                for (int i = 0; i < 4; i++) {
                    int nextRow = row + x[i];
                    int nextColumn = column + y[i];
                    // 边界
                    if (nextRow < 0 || nextRow >= maxRow || nextColumn < 0 || nextColumn >= maxColumn) {
                        continue;
                    }
                    // 下个点满足比当前点大
                    if (matrix[nextRow][nextColumn] < matrix[row][column]) {
                        needJump = true;
                        break;
                    }
                }
                if (needJump) {
                    continue;
                }
                // 注意这里的状态存储不能试全局的,因为每个点都是一个dfs
                // System.out.println(String.format("row:%d column:%d", row, column));
                maxDepth = Math.max(maxDepth, dfs(row, column, maxRow, maxColumn, matrix));
            }
        }
        return maxDepth;
    }

    private int dfs(int row, int column, int maxRow, int maxColumn, int[][] matrix) {
        if (map.containsKey(new Pair(row, column))) {
            return map.get(new Pair(row, column));
        }
        int currentDepth = 1;
        // 四个方向走
        for (int i = 0; i < 4; i++) {
            int nextRow = row + x[i];
            int nextColumn = column + y[i];
            // 边界
            if (nextRow < 0 || nextRow >= maxRow || nextColumn < 0 || nextColumn >= maxColumn) {
                continue;
            }
            // 下个点满足比当前点大
            if (matrix[nextRow][nextColumn] > matrix[row][column]) {
                Pair<Integer, Integer> pair = new Pair<>(nextRow, nextColumn);
                // System.out.println(String.format("dfs nextRow:%d nextColumn:%d", nextRow, nextColumn));
                currentDepth = Math.max(currentDepth, dfs(nextRow, nextColumn, maxRow, maxColumn, matrix) + 1);
            }
        }
        // System.out.println(currentDepth);
        map.put(new Pair(row, column), currentDepth);
        return currentDepth;
    }
}
